package day4;

public class demo2 {
    public static void main(String[] args) {



    }


    public boolean vis[][];
    public int m,n;
    char[] word;

    int[]dy={0,0,1,-1};
    int[]dx={1,-1,0,0};

    public boolean exist(String[] board,String _word){
m=board.length;
n=board[0].length();
        word=_word.toCharArray();
        vis=new boolean[m][n];
        for (int i = 0; i <m ; i++) {
            for (int j = 0; j <n ; j++) {
if (board[i].charAt(j)==word[0]){
    if(dfs(board,i,j,0)){
        return true;
    }
}
            }
        }
        return false;
    }

    public boolean dfs(String[]board,int i,int j,int pos){
        if(pos==word.length-1){
            return true;
        }
        vis[i][j]=true;
        for (int k = 0; k <4 ; k++) {
            int x=dx[k];
            int y=dy[k];
            if(j+x>-1&&j+x<n&&i+y>-1&&i+y<m&&board[y+i].charAt(x+j)==word[pos+1]&&!vis[i+y][j+x]){
             return  dfs(board,i+y,j+x,pos+1);
            }
        }
        vis[i][j]=false;
        return false;
    }
}
